package com.wzq.str;

public class KMPTest {

    private static int[] getNext2(String p){
        if(p==null || p.length()==0){
            return null;
        }

        int len = p.length();
        int[] next = new int[len];
        next[0]=-1;
        for (int subLen=1;subLen<len; subLen++){
            int l = next[subLen-1];
            while(l >= 0){
                if(p.charAt(subLen-1) == p.charAt(l)){
                    next[subLen] = l+1;
                    break;
                }
                l--;
            }
        }
        return next;
    }

    private static int[] getNext(String p){
        int len = p.length();
        int[] next = new int[len];
        next[0]=-1;next[1]=0;
        for (int subLen=2;subLen<len; subLen++){
            if(p.charAt(next[subLen-1]) == p.charAt(subLen-1)){
                next[subLen] = next[subLen-1]+1;
            }else{
                int l = next[subLen-1];
                while(l >= 0){
                    int j=0;
                    while (j<l && p.charAt(j) == p.charAt(subLen-l+j)){
                        j++;
                    }
                    if(j == l){
                        next[subLen]=l;
                        break;
                    }
                    l--;
                }
            }
        }
        return next;
    }

    public static int kmp(String str,String p){
        int[] next = getNext2(p);
        int i=0,j=0;
        while (i<str.length()){
            if(str.charAt(i) == p.charAt(j)){
                i++;j++;
            }else{
                if(next[j] == -1){
                    i++;
                }else{
                    j = next[j];
                }
            }
            if(p.length() == j){
                return i-j;
            }
        }
        return -1;
    }

    public static int kmp1(String str,String p){

       /* int len = p.length();
        int[] next = new int[len];
        next[0] = 0;
        for (int subLen =2 ;subLen<=len; subLen++){
            if(p.charAt(next[subLen-2]) == p.charAt(subLen-1)){
                next[subLen-1] = next[subLen-2]+1;
            }else if(p.charAt(0) == p.charAt(subLen-1)) {
                next[subLen-1]=1;
            }else{
                next[subLen-1]=0;
            }
        }*/

        int len = p.length();
        int[] next = new int[len];
        next[0] = 0;
        int i=0,j=1;
        while (j<len){
            if(p.charAt(i) == p.charAt(j)){
                next[j] = next[j-1]+1;
                i++;
                j++;
            }else if(p.charAt(0) == p.charAt(j)){
                next[j]=1;
            }else{
                next[j]=0;
            }
        }

        return next[0];

    }

    private static int[] getNext3(String p){
        if(p==null || p.length()==0){
            return null;
        }

        int len = p.length();
        int[] next = new int[len];
        next[0] = -1;
        int i = 0;
        int j = -1;
        while (i < p.length() - 1) {
            if( j == -1 || p.charAt(i) == p.charAt(j)){
                next[++i] = ++j;
            }
            else{
                j = next[j];
            }
        }
        return next;
    }


    public static void main(String[] args) {
        /*int i = kmp("acabaabaabcaccaabc","abaabcac");*/
        /*int i = kmp("mississippi","issip");*/
        /*int i = kmp("aabaaabaaac","aabaaac");

        System.out.println(i);*/

        getNext3("acabacacd");
    }



}
